/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */


#ifndef _BST_H_
#define _BST_H_

#define NDEBUG
#include <cassert>

#include "nodobst.h"

template <class T>
class Bst {
public:
	Bst();
	~Bst();

	//Operatori
	void inserisci( T );
	bool appartiene( T );
	void cancella( T ) throw (char const *);
	T minimo() throw (char const *) ;
	T massimo() throw (char const *) ;
	T predecessore( T ) throw (char const *);
	T successore( T ) throw (char const *);
	void leggi();

	//operatori personalizzati
	void print();
	void cancellaTutto();


private:

	typedef NodoBST<T> * posizione;

	bool appartiene( T, posizione );
	void cancella( T, posizione );
	void print( posizione );
	T minimo( posizione );
	T massimo( posizione );
	void visitaSimmetrica( posizione );
	posizione trova( T, posizione );

	posizione radice;
};



/*****************************
 *        DEFINIZIONI        *
 *  dei metodi di Alberobin  *
 *****************************/


template <class T>
Bst<T>::Bst() {
	radice = NULL;
}

template <class T>
Bst<T>::~Bst() {
	cancellaTutto();
}

template <class T>
void Bst<T>::cancellaTutto() {
	while ( radice != NULL ) {
		cancella( minimo() );
	}
}

template <class T>
bool Bst<T>::appartiene( T elem ) {
	return appartiene( elem, radice );
}


template <class T>
void Bst<T>::cancella( T elem ) throw (char const *) {
	if ( !appartiene(elem) )
		throw "Elemento non presente";
	else
		cancella( elem, radice );
}


template <class T>
void Bst<T>::inserisci( T elem ) {
	posizione pos = radice;
	posizione padre = radice;

	posizione temp = new NodoBST<T>();
	temp->setValue( elem );

	if (radice == NULL)
		radice = temp;
	else {
		while ( pos != NULL ) {
			padre = pos ;
			pos = ( temp->getValue() <= pos->getValue() ) ?
					pos->getFiglioSinistro() :
					pos->getFiglioDestro() ;
		}

		assert( pos == NULL );

		temp->setPadre( padre );
		( temp->getValue() <= padre->getValue() ) ?
				padre->setFiglioSinistro( temp ) :
				padre->setFiglioDestro( temp );
	}

}


template <class T>
T Bst<T>::minimo() throw (char const *) {
	if ( radice == NULL ) {
		throw "BST Vuoto.";
	} else {
		return minimo(radice);
	}
}

template <class T>
T Bst<T>::massimo() throw (char const *) {
	if ( radice == NULL ) {
		throw "BST Vuoto.";
	} else {
		return massimo(radice);
	}
}


template <class T>
T Bst<T>::predecessore( T elem ) throw (char const *) {
	if ( !appartiene(elem) )
		throw "Elemento non presente";
	else
		if ( elem == minimo() )
			throw "L'elemento non ha predecessori.";
		else {
			posizione pos = trova(elem, radice);

			assert(pos!=NULL);

			if ( pos->getFiglioSinistro() != NULL )
				return massimo( pos->getFiglioSinistro() );
			else {
				assert (pos!=NULL);
				assert (pos->getPadre()!=NULL);
				return pos->getPadre()->getValue();
			}
		}
}


template <class T>
T Bst<T>::successore( T elem ) throw (char const *) {
	if ( !appartiene(elem) )
		throw "Elemento non presente";
	else
		if ( elem == massimo() )
			throw "L'elemento non ha successori.";
		else {
			posizione pos = trova(elem, radice);

			assert(pos!=NULL);

			if ( pos->getFiglioDestro() != NULL )
				return minimo( pos->getFiglioDestro() );
			else
				return pos->getPadre()->getValue();
		}
}




template <class T>
void Bst<T>::print() {
	print( radice );
}


template <class T>
void Bst<T>::leggi() {
	visitaSimmetrica( radice );
	cout << endl;
}




/*****************************
 *    OPERATORI PRIVATI      *
 *****************************/

template <class T>
bool Bst<T>::appartiene( T elem, posizione pos ) {
	if ( pos == NULL ) {
		return false;
	} else {
		if ( elem == pos->getValue() )
			return true;
		else if ( elem < pos->getValue() )
			return appartiene( elem, pos->getFiglioSinistro() ) ;
		else
			return appartiene( elem, pos->getFiglioDestro() ) ;
	}
}





template <class T>
void Bst<T>::cancella( T elem, posizione pos ) {

	assert( appartiene(elem) );

	pos = trova(elem, radice);

	assert(pos!=NULL);

	bool p = ( pos->getFiglioSinistro() == NULL ) ;
	bool q = ( pos->getFiglioDestro() == NULL ) ;

	bool foglia = ( p && q ) ;
	if ( foglia ) {
		if ( pos->getPadre() != NULL ) { //se non è radice
			if ( pos->getPadre()->getFiglioSinistro() == pos )
				pos->getPadre()->setFiglioSinistro( NULL );
			else
				pos->getPadre()->setFiglioDestro( NULL );
		} else { //se è radice
			radice = NULL;
		}
		delete pos;
	}

	bool unSoloFiglio = ( ( p || q ) && !( p && q ) ); //XOR
	//se ha un solo figlio
	if ( unSoloFiglio ) {

		//se non è radice
		if ( pos->getPadre() != NULL ) {

			//se pos è figlio sinistro del padre
			if ( pos->getPadre()->getFiglioSinistro() == pos )
				if (p) { //se sinistro vuoto
					pos->getPadre()->setFiglioSinistro( pos->getFiglioDestro() );
					pos->getFiglioDestro()->setPadre( pos->getPadre() );
				} else {
					pos->getPadre()->setFiglioSinistro( pos->getFiglioSinistro() );
					pos->getFiglioSinistro()->setPadre( pos->getPadre() );
				}
			else //se è figlio destro
				if (p) { //se sinistro vuoto
					pos->getPadre()->setFiglioDestro( pos->getFiglioDestro() );
					pos->getFiglioDestro()->setPadre( pos->getPadre() );
				} else {
					assert( q ); //il destro è per forza vuoto
					pos->getPadre()->setFiglioDestro( pos->getFiglioSinistro() );
					pos->getFiglioSinistro()->setPadre( pos->getPadre() );
				}

		} else { //se è radice
			if (p) { //se sinistro vuoto
				radice = pos->getFiglioDestro() ;
				pos->getFiglioDestro()->setPadre(NULL);
			} else {
				radice = pos->getFiglioSinistro() ;
				pos->getFiglioSinistro()->setPadre(NULL);
			}
		}
		delete pos;
	}

	bool dueFigli = ( ! ( p || q ) ) ;
	if ( dueFigli ) {
		T temp = predecessore( elem );
		cancella( temp );
		pos->setValue( temp );
	}
}


template <class T>
void Bst<T>::print(posizione nodo) {

	cout << "(" ;

	if ( nodo != NULL ) {
		cout << nodo->getValue() ;

		if ( (nodo->getFiglioSinistro()!=NULL)
			|| (nodo->getFiglioDestro()!=NULL) ) {

			print( nodo->getFiglioSinistro() );
			print( nodo->getFiglioDestro() );
		}

	} else {}

	cout << ")" ;
}





template <class T>
void Bst<T>::visitaSimmetrica(posizione nodo) {

	if ( radice != NULL ) {
		if ( nodo != NULL ) {
				visitaSimmetrica( nodo->getFiglioSinistro() );
				cout << nodo->getValue() << " " ;
				visitaSimmetrica( nodo->getFiglioDestro() );
		}
	}
}


template <class T>
T Bst<T>::minimo( posizione pos ) {
	if ( pos->getFiglioSinistro() == NULL ) {
		return pos->getValue();
	} else {
		pos = pos->getFiglioSinistro();
		return minimo( pos ) ;
	}
}




template <class T>
T Bst<T>::massimo( posizione pos ) {
	if ( pos->getFiglioDestro() == NULL ) {
		return pos->getValue();
	} else {
		pos = pos->getFiglioDestro();
		return massimo( pos ) ;
	}
}


template <class T>
typename Bst<T>::posizione Bst<T>::trova( T elem, posizione pos ) {
	assert( pos!=NULL );
	if (pos->getValue() != elem) {
		posizione p;
		p = ( elem < pos->getValue() ) ?
				pos->getFiglioSinistro() :
				pos->getFiglioDestro() ;
		return trova( elem, p );
	} else
		return pos;
}

#endif // _ALBEROBIN_H_
